package 二叉树练习题;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树翻转
 * <p>
 * 二叉树的镜像就是二叉树对称的二叉树，就是交换每一个非叶子结点的左子树指针和右子树指针，
 * 如下图所示，请写出能实现该功能的代码。
 * 注意：请勿对该树做任何假设，它不一定是平衡树，也不一定有序。
 */
public class Test {

    public static void reversalTree(BiTNode root) {
        if (root == null) {
            return;
        }
        reversalTree(root.lchild);
        reversalTree(root.rchild);
        BiTNode tmp = root.lchild;
        root.lchild = root.rchild;
        root.rchild = tmp;
    }

    public static BiTNode arrayToTree(int[] arr, int start, int end) {
        BiTNode root = null;
        if (end >= start) {
            root = new BiTNode();
            int mid = (start + end + 1) / 2;
            //数据的根节点为数组中间元素
            root.data = arr[mid];
            //递归用树的左半部分数组构造root的左子树
            root.lchild = arrayToTree(arr, start, mid - 1);
            //递归用树的右半部分数组构造root的右子树
            root.rchild = arrayToTree(arr, mid + 1, end);
        } else {
            root = null;
        }
        return root;
    }

    /**
     * 打印树的节点数据
     *
     * @param root
     */
    public static void printTreeLayer(BiTNode root) {
        if (root == null) {
            return;
        }
        BiTNode p;
        Queue<BiTNode> queue = new LinkedList<BiTNode>();
        //树的根节点进入队列
        queue.offer(root);
        while (queue.size() > 0) {
            p = queue.poll();
            //访问当前节点数据
            System.out.print(p.data + " ");
            //如果这个节点的左孩子不为空则入队列
            if (p.lchild != null) {
                queue.offer(p.lchild);
            }
            //如果这个节点的右孩子不为空则入队列
            if (p.rchild != null) {
                queue.offer(p.rchild);
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 6, 7};
        BiTNode root;
        //数组转二叉树
        root = arrayToTree(arr, 0, arr.length - 1);
        System.out.print("二叉树层序遍历结果：");
        printTreeLayer(root);
        System.out.println();
        reversalTree(root);
        System.out.print("反转后二叉树层序遍历结果为：");
        printTreeLayer(root);
    }
}
